package top.serms.leetcode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;

/**
 * @Author: SerMs
 * @Date: 2024/06/25 09 13
 * @Email: 1839928782@qq.com
 * @Blog: https://serms.top
 * <h1>两数之和</h1>
 **/
public class LeetCodeTwoSum {

    // 暴力解法
    public static int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if ((nums[i] + nums[j]) == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }


    // 哈希表
    public static int[] twoSumHashTable(int[] nums, int target) {
        Map<Integer, Integer> hashTable = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; ++i) {
            if (hashTable.containsKey(target - nums[i])) {
                return new int[]{hashTable.get(target - nums[i]), i};
            }
            hashTable.put(nums[i], i);
        }
        return new int[0];
    }
    // 生成随机数组
    public static int[] generateRandomArray(int size, int maxValue) {
        Random random = new Random();
        int[] array = new int[size];
        for (int i = 0; i < size; i++) {
            array[i] = random.nextInt(maxValue + 1);
        }
        return array;
    }

    // 对数器
    public static void main(String[] args) {
        int testTime = 10000;
        int maxSize = 100;
        int maxValue = 100;
        boolean allPass = true;

        for (int i = 0; i < testTime; i++) {
            int[] nums = generateRandomArray(100, 50);
            Random random = new Random();
            int target = nums[23]+ nums[80];

            int[] answer1 = twoSum(nums, target);
            int[] answer3 = twoSumHashTable(nums, target);

            if (!Arrays.equals(answer1, answer3)) {
                allPass = false;
                System.out.println("Test failed!");
                System.out.println("nums: " + Arrays.toString(nums));
                System.out.println("target: " + target);
                System.out.println("twoSum: " + Arrays.toString(answer1));
                System.out.println(nums[answer1[0]] + " " + answer1[1]);
                System.out.println("twoSumHashTable: " + Arrays.toString(answer3));
                System.out.println(nums[answer3[0]] + " " + answer3[1]);
                break;
            }
        }

        if (allPass) {
            System.out.println("All tests passed!");
        }
    }
}

